-- Module      :  Data.Ix
-- Copyright   :  (c) The University of Glasgow 2001
-- License     :  BSD Style, full text in LICENSE.txt
-- Adapted to Frege by Lech Głowiak

package Data.Ix where

import frege.data.Tuples public()

{-- The 'Ix' class is used to map a contiguous subrange of values in
    a type onto integers.  It is used primarily for array indexing.
    (see the array package).
    
    The first argument @(l,u)@ of each of these operations is a pair
    specifying the lower and upper bounds of a contiguous subrange of values.
    An implementation is entitled to assume the following laws about these
    operations:

    > inRange (l,u) i == elem i (range (l,u))

    > range (l,u) !! index (l,u) i == i
    , when
    > inRange (l,u) i

    > map (index (l,u)) (range (l,u)) == [0..rangeSize (l,u)-1]

    > rangeSize (l,u) == length (range (l,u))
-}
class Ord a => Ix a where

    --- The list of values in the subrange defined by a bounding pair.
    range               :: (a,a) -> [a]
    --- The position of a subscript in the subrange.
    index               :: (a,a) -> a -> Int
    --- Like 'index', but without checking that the value is in range.
    unsafeIndex         :: (a,a) -> a -> Int
    --- Returns 'True' the given subscript lies in the range defined the bounding pair.
    inRange             :: (a,a) -> a -> Bool
    --- The size of the subrange defined by a bounding pair.
    rangeSize           :: (a,a) -> Int
    --- like 'rangeSize', but without checking that the upper bound is in range.
    unsafeRangeSize     :: (a,a) -> Int

    {-- Must specify one of index, unsafeIndex

         'index' is typically over-ridden in instances, with essentially
         the same code, but using indexError instead of error
         Reason: we have 'Show' at the instances
    -}
    index b i | inRange b i = unsafeIndex b i
              | otherwise   = error "Error in array index"

    unsafeIndex b i = index b i

    rangeSize (b@(_,h)) | inRange b h = unsafeIndex b h + 1
                        | otherwise   = 0       -- This case is only here to
                                                -- check for an empty range
        -- NB: replacing (inRange b h) by (l <= h) fails for
        --     tuples.  E.g.  (1,2) <= (2,1) but the range is empty

    unsafeRangeSize (b@(_,h)) = unsafeIndex b h + 1

--- nowarn: diverge
{-Note [Out-of-bounds error messages]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The default method for 'index' generates hopelessIndexError, because
Ix doesn't have Show as a superclass.  For particular base types we
can do better, so we override the default method for index.
-}

-- Abstract these errors from the relevant index functions so that
-- the guts of the function will be small enough to inline.

indexError :: Show a => (a,a) -> a -> String -> b
indexError rng i tp
  = error (showString "Ix{" . showString tp . showString "}.index: Index " .
           showParen true (showsPrec 0 i) .
           showString " out of range " $
           showParen true (showsPrec 0 rng) "")

--  leads to errors during initialization, as the frge compiler
--  thinks it can compute the 'Int' value right away ...
--hopelessIndexError :: Int -- Try to use 'indexError' instead!
--hopelessIndexError = error "Error in array index"


instance Ix Bool where

    range (m,n) = [m..n]

    unsafeIndex (l,_) i = fromEnum i - fromEnum l

    index b i | inRange b i =  unsafeIndex b i
              | otherwise   =  indexError b i "Bool"

    inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u


instance  Ix Char where

    range (m,n) = [m..n]

    unsafeIndex (m,_) i = fromEnum i - fromEnum m

    index b i | inRange b i =  unsafeIndex b i
              | otherwise   =  indexError b i "Char"

    inRange (m,n) i     =  m <= i && i <= n


instance Ix Int where

    range (m,n) = [m..n]

    unsafeIndex (m,n) i = i - m

    index b i | inRange b i =  unsafeIndex b i
              | otherwise   =  indexError b i "Int"

    inRange (m,n) i     =  m <= i && i <= n


instance Ix Integer where

    range (m,n) = [m..n]

    unsafeIndex (m,_) i   = fromInteger (i - m)

    index b i | inRange b i =  unsafeIndex b i
              | otherwise   =  indexError b i "Integer"

    inRange (m,n) i     =  m <= i && i <= n


instance Ix Ordering where

    range (m,n) = [m..n]

    unsafeIndex (l,_) i = fromEnum i - fromEnum l

    index b i | inRange b i =  unsafeIndex b i
              | otherwise   =  indexError b i "Ordering"

    inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u


instance Ix () where

    range   ((), ())    = [()]

    unsafeIndex   ((), ()) () = 0

    inRange ((), ()) () = true

    index b i = unsafeIndex b i


instance (Ix a, Ix b) => Ix (a, b) where

    range ((l1,l2),(u1,u2)) =
      [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]

    unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
      unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2

    inRange ((l1,l2),(u1,u2)) (i1,i2) =
      inRange (l1,u1) i1 && inRange (l2,u2) i2


instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where

    range ((l1,l2,l3),(u1,u2,u3)) =
        [(i1,i2,i3) | i1 <- range (l1,u1),
                      i2 <- range (l2,u2),
                      i3 <- range (l3,u3)]

    unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
      unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
      unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
      unsafeIndex (l1,u1) i1))

    inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
      inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
      inRange (l3,u3) i3


instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
    range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
      [(i1,i2,i3,i4) | i1 <- range (l1,u1),
                       i2 <- range (l2,u2),
                       i3 <- range (l3,u3),
                       i4 <- range (l4,u4)]

    unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
      unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
      unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
      unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
      unsafeIndex (l1,u1) i1)))

    inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
      inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
      inRange (l3,u3) i3 && inRange (l4,u4) i4

instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
    range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
      [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
                          i2 <- range (l2,u2),
                          i3 <- range (l3,u3),
                          i4 <- range (l4,u4),
                          i5 <- range (l5,u5)]

    unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
      unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
      unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
      unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
      unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
      unsafeIndex (l1,u1) i1))))

    inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
      inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
      inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
      inRange (l5,u5) i5
